package com.longge;

import java.util.ArrayList;

public class IncreasingBSTII {
    
    public TreeNode increasingBST(TreeNode root) {

        ArrayList<Integer> nums = new ArrayList<>();
        dfs(root,nums);
        return buildTree(nums,0);

    }

    private TreeNode buildTree(ArrayList<Integer> nums, int i) {
        if (i==nums.size()) return null;
        TreeNode root = new TreeNode(nums.get(i));
        root.right = buildTree(nums,i+1);
        return root;
    }

    private void dfs(TreeNode root, ArrayList<Integer> nums) {
        
        if (root == null) return;
        
        dfs(root.left,nums);
        nums.add(root.val);
        dfs(root.right,nums);
    }
}
